home *** CD-ROM | disk | FTP | other *** search
/ Workbench Add-On / Workbench Add-On - Volume 1.iso / Dev / SmallTalk / SequenceableCollection.st < prev    next >
Text File  |  1995-08-25  |  10KB  |  353 lines
  1. "======================================================================
  2. |
  3. |   SequenceableCollection Method Definitions
  4. |
  5.  ======================================================================"
  6.  
  7.  
  8. "======================================================================
  9. |
  10. | Copyright (C) 1990, 1991, 1992 Free Software Foundation, Inc.
  11. | Written by Steve Byrne.
  12. |
  13. | This file is part of GNU Smalltalk.
  14. |
  15. | GNU Smalltalk is free software; you can redistribute it and/or modify it
  16. | under the terms of the GNU General Public License as published by the Free
  17. | Software Foundation; either version 1, or (at your option) any later version.
  18. | 
  19. | GNU Smalltalk is distributed in the hope that it will be useful, but WITHOUT
  20. | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  21. | FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  22. | details.
  23. | 
  24. | You should have received a copy of the GNU General Public License along with
  25. | GNU Smalltalk; see the file COPYING.  If not, write to the Free Software
  26. | Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  
  27. |
  28.  ======================================================================"
  29.  
  30.  
  31. "
  32. |     Change Log
  33. | ============================================================================
  34. | Author       Date       Change 
  35. | sbb         16 Mar 91      Class creation now separate statement.
  36. |
  37. | sbb         29 Dec 90      Added hash function.
  38. |
  39. | sbb         29 Dec 90      Added = test to check sub elements for equality.
  40. |
  41. | sbb         20 Sep 90      Fixed indexOfSubCollection (it was off by one and did
  42. |              too much computation.
  43. |
  44. | sbyrne     19 Sep 89      Converted to use real method categories.
  45. |
  46. | sbyrne     25 Apr 89      created.
  47. |
  48. "
  49.  
  50. Collection variableSubclass: #SequenceableCollection
  51.        instanceVariableNames: ''
  52.        classVariableNames: ''
  53.        poolDictionaries: ''
  54.        category: nil
  55. !
  56.  
  57. SequenceableCollection comment: 
  58. 'My instances represent collections of objects that are ordered.  I provide
  59. some access and manipulation methods.' !
  60.  
  61.  
  62. !SequenceableCollection methodsFor: 'basic'!
  63.  
  64. atAll: aCollection put: anObject
  65.     aCollection do: [ :index | self at: index put: anObject ]
  66. !
  67.  
  68. atAllPut: anObject
  69.     1 to: self size do: [ :index | self at: index put: anObject ]
  70. !
  71.  
  72. first
  73.     ^self at: 1
  74. !
  75.  
  76. last
  77.     self size < 1 ifTrue: [ ^self error: 'last not defined with no elements' ].
  78.     ^self at: self size
  79. !
  80.  
  81. indexOf: anElement ifAbsent: exceptionBlock
  82.     1 to: self size do: [ :index | (self at: index) = anElement
  83.                                      ifTrue: [ ^index ] ].
  84.     ^exceptionBlock value
  85. !
  86.  
  87. indexOf: anElement
  88.     ^self indexOf: anElement ifAbsent: [ ^0 ]
  89. !
  90.  
  91. = aCollection
  92.     | size |
  93.     self == aCollection ifTrue: [ ^true ].
  94.     self species == aCollection species ifFalse: [ ^false ].
  95.     (size _ self size) == aCollection size ifFalse: [ ^false ].
  96.     1 to: size do:
  97.     [ :i | (self at: i) = (aCollection at: i)
  98.            ifFalse: [ ^false ] ].
  99.     ^true
  100. !
  101.  
  102. hash
  103.     "Return the hash value of the array"
  104.     "### I don't like this hashing algorithm"
  105.     | hashValue |
  106.     hashValue _ 0.
  107.     self do: [ :element | hashValue _ ((hashValue bitShift: 1)
  108.                                         bitXor:  element hash)
  109.                     bitAnd: 16r1FFFFFFF ].
  110.     ^hashValue
  111. !!
  112.  
  113.  
  114.  
  115. !SequenceableCollection methodsFor: 'nonpublic methods'!
  116.  
  117. matchSubCollection: aSubCollection startingAt: anIndex
  118.     2 to: aSubCollection size do:
  119.         [ :index | (self at: anIndex + index - 1) ~= (aSubCollection at: index)
  120.                    ifTrue: [ ^false ]
  121.     ].
  122.     ^true
  123. !
  124.  
  125. indexOfSubCollection: aSubCollection startingAt: anIndex
  126.     ifAbsent: exceptionBlock
  127.     | selfSize subSize |
  128.     subSize  _ aSubCollection size.
  129.     selfSize _ self size.
  130.     anIndex + subSize - 1 <= selfSize ifTrue:
  131.     [ anIndex to: selfSize - subSize + 1 do:
  132.           [:index | (self at: index) = (aSubCollection at: 1)
  133.                 ifTrue: [(self matchSubCollection: aSubCollection
  134.                        startingAt: index)
  135.                      ifTrue: [^index]
  136.                      ]
  137.                 ]
  138.           ].
  139.     ^exceptionBlock value
  140. !
  141.  
  142. "
  143. ""indexOfSubCollection: aSubCollection startingAt: anIndex
  144. ""                      ifAbsent: exceptionBlock
  145. ""    | selfSize subSize |
  146. ""    subSize _ aSubCollection size.
  147. ""    selfSize _ self size.
  148. ""    anIndex + subSize <= selfSize ifTrue:
  149. ""        [ 1 to: subSize do:
  150. ""            [ :index | (aSubCollection at: index) = (self at: anIndex + index - 1)
  151. ""                    ifTrue: [ (self matchSubCollection: aSubCollection
  152. ""                           startingAt: index)
  153. ""                       ifTrue: [ ^index ]
  154. ""                        ]
  155. ""        ] 
  156. ""        ].
  157. ""    ^exceptionBlock value
  158. ""!
  159. "
  160. indexOfSubCollection: aSubCollection startingAt: anIndex
  161.     ^self indexOfSubCollection: aSubCollection startingAt: anIndex
  162.         ifAbsent: [ ^0 ]
  163. !
  164.  
  165. replaceFrom: start to: stop with: replacementCollection startingAt: repStart
  166.     (self == replacementCollection and: [ repStart ~= 1 ])
  167.         ifTrue: [ ^self error: 'replaceFrom:to:with:startingAt: called for 
  168. in-place replacement, but starting index was not 1' ].
  169.     "speed this up by making it zero based, otherwise we have to subtract
  170.      1 from each use of index, and add one to the range"
  171.     0 to: stop - start  do:
  172.         [ :index |
  173.       self at: (start + index)
  174.                put: (replacementCollection at: (repStart + index)) ]
  175. !
  176.  
  177. replaceFrom: start to: stop with: replacementCollection
  178.     (stop - start + 1) ~= replacementCollection size
  179.         ifTrue: [ ^self error: 'replacement range does not equal size of
  180. replacement collection' ].
  181.     self replaceFrom: start to: stop with: replacementCollection startingAt: 1
  182. !!
  183.  
  184.  
  185.  
  186. !SequenceableCollection methodsFor: 'copying SequenceableCollections'!
  187.  
  188. , aSequenceableCollection
  189.     | newCollection |
  190.     newCollection _ self species new: (self size + aSequenceableCollection size).
  191.     newCollection replaceFrom: 1 to: self size with: self.
  192.     newCollection replaceFrom: (self size) + 1
  193.                   to: self size + aSequenceableCollection size
  194.           with: aSequenceableCollection.
  195.     ^newCollection
  196. !
  197.  
  198. copyFrom: start to: stop
  199.     | newCollection len |
  200.     len _ stop - start + 1.
  201.     newCollection _ self species new: len.
  202.     newCollection replaceFrom: 1 to: len with: self startingAt: start.
  203.     ^newCollection
  204. !
  205.  
  206. copyReplaceAll: oldSubCollection with: newSubCollection
  207.     | numOld newCollection sizeDifference newSubSize oldSubSize
  208.       newStart oldStart copySize index |
  209.     numOld _ self countSubCollectionOccurrencesOf: oldSubCollection.
  210.     newSubSize _ newSubCollection size.
  211.     sizeDifference _ newSubSize - oldSubCollection size + 1.
  212.     newCollection _ self species new: (self size - (sizeDifference * numOld)).
  213.     oldStart _ newStart _ 1.
  214.     [ index _ self indexOfSubCollection: oldSubCollection
  215.                    startingAt: oldStart.
  216.       index > 0 ] whileTrue:
  217.         [ copySize _ index - oldStart + 1.
  218.       newCollection replaceFrom: newStart
  219.                     to: newStart + copySize - 1
  220.             with: self
  221.             startingAt: oldStart.
  222.       newStart _ newStart + copySize - 1.
  223.       newCollection replaceFrom: newStart
  224.                     to: newStart + newSubSize - 1
  225.             with newSubCollection.
  226.           oldStart _ oldStart + copySize.
  227.           newStart _ newStart + newSubSize ].
  228.     "Copy the remaining part of self onto the tail of the new collection."
  229.     newCollection replaceFrom: newStart
  230.                  to: newCollection size
  231.          with: self
  232.          startingAt: oldStart.
  233.     ^newCollection
  234. !
  235.  
  236. copyReplaceFrom: start to: stop with: replacementCollection
  237.     | newCollection newSize repSize |
  238.     "### check for bounds "
  239.     repSize _ replacementCollection size.
  240.     newSize _ self size + repSize - (stop - start + 1).
  241.     newCollection _ self species new: newSize.
  242.     newCollection replaceFrom: 1 to: start - 1 with: self startingAt: 1.
  243.     newCollection replaceFrom: start
  244.                   to: start + repSize - 1
  245.           with: replacementCollection.
  246.     newCollection replaceFrom: start + repSize
  247.                   to: newCollection size
  248.           with: self
  249.           startingAt: stop + 1.
  250.     ^newCollection
  251. !
  252.  
  253. copyWith: newElement
  254.     | newCollection len |
  255.     len _ self size + 1.
  256.     newCollection _ self species new: len.
  257.     newCollection replaceFrom: 1 to: self size with: self.
  258.     newCollection at: len put: newElement.
  259.     ^newCollection
  260. !
  261.  
  262. copyWithout: oldElement
  263.     | newCollection numOccurrences i |
  264.     numOccurrences _ 0.
  265.     self do:
  266.         [ :element |
  267.       element = oldElement
  268.         ifTrue: [ numOccurrences _ numOccurrences + 1 ] ].
  269.     newCollection _ self species new: (self size - numOccurrences).
  270.     i _ 1.
  271.     self do:
  272.         [ :element |
  273.       element ~= oldElement
  274.         ifTrue: [ newCollection at: i put: element.
  275.                   i _ i + 1 ]
  276.     ].
  277.     ^newCollection
  278. !!
  279.  
  280.  
  281.  
  282. !SequenceableCollection methodsFor: 'enumerating'!
  283.  
  284. do: aBlock
  285.     "Evaluate aBlock for all elements in the sequenceable collection"
  286.     1 to: self size do:
  287.         [ :i | aBlock value: (self at: i) ]
  288. !
  289.  
  290. findFirst: aBlock
  291.     "Returns the index of the first element of the sequenceable collection
  292.     for which aBlock returns true"
  293.     1 to: self size do:
  294.         [ :i | (aBlock value: (self at: i))
  295.              ifTrue: [ ^i ] ].
  296.     ^0
  297. !
  298.  
  299. findLast: aBlock
  300.     self size to: 1 by: -1 do:
  301.         [ :i | (aBlock value: (self at: i))
  302.              ifTrue: [ ^i ] ].
  303.     ^0
  304. !
  305.  
  306. reverseDo: aBlock
  307.     self size to: 1 by: -1 do:
  308.         [ :i | aBlock value: (self at: i) ]
  309. !
  310.  
  311. with: aSequenceableCollection do: aBlock
  312.     self size = aSequenceableCollection size
  313.         ifFalse:
  314.         [ ^self error: 'sequenceable collections must have same size' ].
  315.     1 to: self size do:
  316.         [ :i | aBlock value: (self at: i)
  317.                   value: (aSequenceableCollection at: i) ]
  318. !!
  319.  
  320.  
  321.  
  322. !SequenceableCollection methodsFor: 'private methods'!
  323.  
  324. countSubCollectionOccurrencesOf: aSubCollection
  325.     | colIndex subColIndex count |
  326.     colIndex _ 1.
  327.     count _ 0.
  328.     [ subColIndex _ self indexOfSubCollection: aSubCollection
  329.                          startingAt: colIndex.
  330.       subColIndex > 0 ] whileTrue:
  331.           [ count _ count + 1.
  332.       colIndex _ colIndex + aSubCollection size ].
  333.     ^count
  334. !
  335.  
  336. grow
  337.     | newCollection |
  338. "    self class == ByteArray 
  339.     ifTrue: [  'growing ' print. self basicPrint.
  340.            self basicSize printNl.
  341.            Smalltalk backtrace   ]."
  342.   
  343.     newCollection _ self species new: self basicSize + self growSize.
  344.     newCollection replaceFrom: 1 to: self size with: self.
  345.     ^self become: newCollection
  346. !
  347.     
  348. growSize
  349.     ^10                "a randomly chosed number"
  350.  
  351. !!
  352.  
  353.